package 滑动窗口;

public class LeetCode76_最小覆盖子串 {
    public String minWindow(String s, String t) {
        if(s == null || t == null || s.length() < t.length()) {
            return "";
        }
        int[] need = new int[128];
        // 1. 先将t中的字符放入
        for(int i = 0; i < t.length(); i++) {
            need[t.charAt(i)] ++;
        }
        int l = 0, r = 0, size = Integer.MAX_VALUE,count = t.length(),start = 0;
        // 遍历s
        while(r < s.length()) {
            char c = s.charAt(r);
            if(need[c] > 0) { // 需要c
                count--;
            }
            need[c] --;//把右边字符加入窗口
            if(count == 0) { //此窗口包含了t的所有字符
                while(l < r && need[s.charAt(l)] < 0) {
                    need[s.charAt(l)]++; //释放左边不需要的字符
                    l++;//做窗口右移
                }
                // if(size == 0) {
                //     size = r-l+1;
                // }
                if(r-l+1 < size) { //此时不能再右移了，到达了需要的字符，如果这个更小就更新
                    size = r-l+1;
                    start = l;//记录开始位置
                }
                //l向右移动，重新开始循环找
                need[s.charAt(l)]++;
                l++;
                count++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start,start+size);
    }

    public static void main(String[] args) {
        String s = "";

    }
}
